package C028;

import java.util.Arrays;

/**
 * ClassName: C01
 * Package: C028
 * Description:
 *
 * @Author BCXJ
 * @Create 2024/12/12 21:52
 * @Version 1.0
 * @Since 1.0
 */
public class C01 {


    public static void main(String[] args) {
        int n = 10000;
        int size = 100;
        int length = 20;
        for (int i = 0; i < n; i++) {
            int[] arr1 = randomGenerateArr(size, length);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            int[] arr3 = Arrays.copyOf(arr1, arr1.length);
            sortArray(arr1);
            Arrays.sort(arr2);
            if (!Arrays.equals(arr1, arr2)) {
                System.out.println("error !!!");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                System.out.println(Arrays.toString(arr3));
                return;
            }
        }

        System.out.println("success !!!");

    }
    static int BASE = 2;
    public static int[] randomGenerateArr(int size, int length) {
        int[] ints = new int[length];
        for (int i = 0; i < ints.length; i++) {
            ints[i] = (int) (Math.random() * size);
        }
        return ints;
    }

    public static int[] sortArray(int[] arr) {
        // 寻找最小值
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            min = Math.min(min, arr[i]);
        }

        // 寻找最大值
        int max = arr[0] - min;
        for (int i = 0; i < arr.length; i++) {
            arr[i] -= min;
            max = Math.max(max, arr[i]);
        }
        radixSort(arr, bits(max));
        for (int i = 0; i < arr.length; i++) {
            arr[i] += min;
        }
        return arr;
    }

    private static void radixSort(int[] arr, int bits) {
        int[] cnts = new int[BASE];
        int[] help = new int[arr.length];
        for (int i = 0, offset = 1; i < bits; i++, offset *= BASE) {
            Arrays.fill(cnts, 0);
            for (int j = 0; j < arr.length; j++) {
                cnts[(arr[j] / offset) % BASE]++;
            }

            // 前缀分区数组
            for (int j = 1; j < BASE; j++) {
                cnts[j] = cnts[j] + cnts[j - 1];
            }

            // 该位排序
            for (int j = arr.length - 1; j >= 0; j--) {
                help[--cnts[(arr[j] / offset) % BASE]] = arr[j];
            }
            for (int j = 0; j < arr.length; j++) {
                arr[j] = help[j];
            }
        }
    }

    /**
     * 找出max 有几位数字
     *
     * @param max
     * @return
     */
    private static int bits(int max) {
        int count = 0;
        int mid = BASE;
        while (max != 0) {
            max /= mid;
            count++;
        }
        return count;
    }
}
